package org.zhangyp.n02datastructure.n02LinkedList;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangyp
 * @date 2023/6/7 10:41
 */
public class Test {

    /**
     * 约瑟夫问题
     * N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。
     * 现在问你最后留下的人是谁？
     * 比如N=6，M=5
     * 留下的就是1
     *
     * @param n
     * @param m
     * @return
     */
    public static int joseph(int n, int m) {
        if (n < 1 || m < 1) {
            return 0;
        }
        //创建一个循环链表
        Node<Integer> head = new Node<>(1);
        Node<Integer> cur = head;
        for (int i = 2; i <= n; i++) {
            cur.next = new Node<>(i);
            cur = cur.next;
        }
        //将尾部指向头部
        cur.next = head;

        Node<Integer> pre = cur;
        int loopIndex = 1;
        while (pre.next.value != pre.next.next.value) {
            // 循环m次，干掉一人
            if (loopIndex == m) {
                pre.next = pre.next.next;
                loopIndex = 1;
            }
            pre = pre.next;
            loopIndex++;
        }
        //最后剩下一个值
        return pre.value;
    }

    public static void main(String[] args) {
        System.out.println(joseph(6, 5));
        List<String> list = new ArrayList<>();
        /*list.sort();*/
    }
}
